package com.wty.mianshi.recursion;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 从某个集合中随机选取 n个数 进行组合
 */
public class Combinations {


    /**
     * [1,2,3,4]
     *
     * @param selectedList
     * @param dataList
     * @param n
     */
    public void combinations(List<Integer> selectedList, List<Integer> dataList, int n) {


        if (n == 0) {
            for (Integer i : selectedList) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        if (dataList.isEmpty() || dataList.size() < n || n < 0) {
            return;
        }


        //第一种情况，选择上了第一个元素，剩余元素中选n-1个
        selectedList.add(dataList.get(0));
        combinations(selectedList, dataList.subList(1, dataList.size()), n - 1);

        //第二种情况，没选择上第一个元素，剩余元素中选n个
        //两种情况都列出来输出,没选上的话把选上的剔除掉，然后从剩下来的里面选
        //就是两种情况各输出一次
        selectedList.remove(selectedList.size() - 1);
        combinations(selectedList, dataList.subList(1, dataList.size()), n);


    }


    public static void main(String args[]) {
        Combinations comb = new Combinations();

        System.out.println("Testing normal data.");
        comb.combinations(
                new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 2);
        System.out.println("==========");

        System.out.println("Testing empty source data.");
        comb.combinations(
                new ArrayList<>(), new ArrayList<>(), 2);
        System.out.println("==========");
        comb.combinations(
                new ArrayList<>(), new ArrayList<>(), 0);
        System.out.println("==========");

        System.out.println("Selecting 1 and 0 elements.");
        comb.combinations(
                new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 1);
        System.out.println("==========");
        comb.combinations(
                new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 0);
        System.out.println("==========");

        System.out.println("Testing large data");
        comb.combinations(
                new ArrayList<>(),
                Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 4);
    }

}
